package q332_findItinerary;

import java.util.*;

public class Solution {
    private Deque<String> res;
    private Map<String, Map<String, Integer>> map;


    public List<String> findItinerary(List<List<String>> tickets) {
        // map中的参数意义分别为 <出发机场 , <到达机场, 当前已使用的航班的次数>>
        map = new HashMap<String, Map<String, Integer>>();
        res = new LinkedList<>();
        /*
        这里的循环将会遍历我们的每一张机票：
        机票的结构是 出发机场 -> 到达机场
         */
        for(List<String> t : tickets){
            Map<String, Integer> temp;
            /*
            如果map中已经存储了这一张机票的出发机场作为Key
            这里我们以 a - b 和 a - c 为例
            首先遇到t = a - b时，map中无法获得对应的key
            此时temp初始化，然后放入 <b, 1>
            map 放入了 <a, <b, 1>>
            然后遍历到第二张机票为t = a - c
            首先temp将被取出为<b, 1>
            此时t.get(1) 是 c
            于是temp重置为<c, 0 + 1>
            最后则是是<a, <c, 1>,<b, 1>>放入map

            但是如果有多个a - b 就会被放入类似于<a, <b, 2>>的值

            还需要注意的是 这里所使用的TreeMap能够帮助我们直接实现字典序
             */
            if(map.containsKey(t.get(0))){
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            }else{
                temp = new TreeMap<>();//升序Map
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);

        }
        // 起点必须是JFK
        res.add("JFK");
        // 只需要size即可开始循环
        backTracking(tickets.size());

        return new ArrayList<>(res);
    }

    private boolean backTracking(int ticketNum){
        // 每张票代表两个城市的连接，如果res达到了连接的最大值，就应该结束
        // 例如 1-2 2-3 3-4 那么res到4个的时候就应该满了
        if(res.size() == ticketNum + 1){
            return true;
        }
        // 每次开始找下一个机场的位置，肯定是从res中最后到达的机场连接的开始找
        // 此时这个机场就被设计为出发机场
        // 所以是getLast
        String last = res.getLast();
        if(map.containsKey(last)){// 防止出现null

            // 遍历同一个机场起飞的所有entry 例如之前存入的有<a, (b,1)(c,1)...>
            for(Map.Entry<String, Integer> target : map.get(last).entrySet()){
                int count = target.getValue();
                if(count > 0){
                    res.add(target.getKey());
                    target.setValue(count - 1);
                    if(backTracking(ticketNum)) return true;
                    res.removeLast();
                    target.setValue(count);
                }
            }


        }
        // 找不到下一个连接的就直接返回false了
        return false;
    }


}
